package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

import java.util.Arrays;

/**
 * @author tzp
 * @since 2020/9/22
 */
public class LC494 implements DynamicProblem {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = Arrays.stream(nums).sum();
        if (S > sum) return 0;
        int[][] dp = new int[nums.length][4000 + S + 1];
        for (int[] row : dp) Arrays.fill(row, -1);
        return re(nums, 0, S, dp);
    }

    public int re(int[] nums, int start, int S, int[][] dp) {
        if (start >= nums.length) return 0;
        if (dp[start][2000 + S] != -1) return dp[start][2000 + S];

        if (start == nums.length - 1) {
            int ways = 0;
            if (nums[start] == S) ways++;
            if (nums[start] == -S) ways++;
            dp[start][2000 + S] = ways;
            return ways;
        } else {
            int ways = re(nums, start + 1, S - nums[start], dp) +
                    re(nums, start + 1, S + nums[start], dp);
            dp[start][2000 + S] = ways;
            return ways;
        }
    }

    public static void main(String[] args) {
//        System.out.println(new LC494().findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
        System.out.println(new LC494().findTargetSumWays(new int[]{1, 0}, 1));
    }
}
